package Greedy.Medium;

public class LC0055 {
    /**
     * 贪心算法。考虑下一步的目标位置，目标位置的好坏可以用 相比当前位置的前进步数+该位置可跳跃距离 来衡量。
     * 时间复杂度N^2。
     */
    public boolean canJump(int[] nums) {
        int ptr = 0;
        while (true) {
            if (ptr + nums[ptr] >= nums.length - 1) return true;
            else if (ptr < nums.length && nums[ptr] == 0) return false;
            int maxScore = 1 + nums[ptr + 1], bestDest = ptr + 1;
            for (int i = ptr + 2; i <= ptr + nums[ptr]; i++) {
                int score = i - ptr + nums[i];
                if (score > maxScore) {
                    maxScore = score;
                    bestDest = i;
                }
            }
            ptr = bestDest;
        }
    }

    /**
     * Ikaruga@LeetCode的解法。本质上是动态规划，dp[i]表示从[0,i]的所有位置出发，能够到达的最远位置。
     */
    public boolean canJumpOptimized(int[] nums) {
        if (nums.length == 1) return true;

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            if (i > dp[i - 1]) return false;
            dp[i] = Math.max(dp[i - 1], i + nums[i]);
            if (dp[i] >= nums.length - 1) return true;
        }

        return dp[nums.length - 2] >= nums.length - 1;
    }
}
